1020B - Badge - CodeForces Solution


brute force dfs and similar graphs *1000

Please click on ads to support us..

Python Code:

num = int(input())
students = [int(x) for x in input().split()]
res = []

for i in range(num):
    curr = i + 1
    temp = set()
    while curr not in temp:
        temp.add(curr)
        curr = students[curr - 1]
    res.append(curr)

print(*res)
 		  						 	 				 		 						 		

C++ Code:

/** Read statement carefully **/

#include <bits/stdc++.h>
using namespace std;

#define     debug(x)            cout<< #x << " = " << x <<endl;
#define     ll                  long long
#define     yes                 cout<< "Yes" << "\n"
#define     no                  cout<< "No"  << "\n"
#define     eps                 1e-7
#define     pb                  push_back
#define     F                   first
#define     S                   second
#define     endl                "\n"

const int sz  = 2e5 + 5;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll  Inf = 1e18;
ll dr[] = {-1, +1, 0,   0};
ll dc[] = { 0,  0, +1, -1};

ll n;
ll ara[1005];
map< ll, ll > vis;

ll get(ll u) {
    if(ara[u] == u or vis[u]) {
        return u;
    }
    vis[u] = 1;
    return u = get( ara[u] );

}

void solve() {

    cin>> n;
    for(ll i = 0; i < n; i ++) cin>> ara[i + 1];
    for(ll i = 1; i <= n; i ++) {
        vis.clear();
        cout<< get(i) << ' ';
    }
    cout<< endl;

}


int32_t main()
{

    ios::sync_with_stdio(false);cin.tie(0);
    ll T; T = 1;
    //cin >> T;
    while(T --) {
        solve();

    }


    return 0;

}


Comments

Submit
0 Comments
More Questions

1612A - Distance
520A - Pangram
124A - The number of positions
1041A - Heist
901A - Hashing Trees
1283A - Minutes Before the New Year
1654D - Potion Brewing Class
1107B - Digital root
25A - IQ test
785A - Anton and Polyhedrons
1542B - Plus and Multiply
306A - Candies
1651C - Fault-tolerant Network
870A - Search for Pretty Integers
1174A - Ehab Fails to Be Thanos
1169A - Circle Metro
780C - Andryusha and Colored Balloons
1153A - Serval and Bus
1487C - Minimum Ties
1136A - Nastya Is Reading a Book
1353B - Two Arrays And Swaps
1490E - Accidental Victory
1335A - Candies and Two Sisters
96B - Lucky Numbers (easy)
1151B - Dima and a Bad XOR
1435B - A New Technique
1633A - Div 7
268A - Games
1062B - Math
1294C - Product of Three Numbers